package com.example.demo.arithmetic.algorithm.sort2024;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] a = new int[]{9, 3, 7, 2, 8, 5, 1, 4};
        sort(a);
        System.out.println(Arrays.toString(a));
    }

    public static void sort(int[] a) {
        int[] temp = new int[a.length];
        split(a, 0, a.length - 1, temp);
    }

    private static void split(int[] a, int left, int right, int[] temp) {
        if (left == right) {
            return;
        }
        int m = (left + right) >>> 1;
        split(a, left, m, temp);
        split(a, m + 1, right, temp);
        merge(a, left, m, right, temp);
    }

    private static void merge(int[] a, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int k = left;

        while (i <= mid && j <= right) {
            if (a[i] <= a[j]) {
                temp[k] = a[i];
                i++;
            } else {
                temp[k] = a[j];
                j++;
            }
            k++;
        }

        while (i <= mid) {
            temp[k] = a[i];
            i++;
            k++;
        }

        while (j <= right) {
            temp[k] = a[j];
            j++;
            k++;
        }

        System.arraycopy(temp, left, a, left, right - left + 1);
    }
}
